Introduction to Machine Learning

Chapter 08: Decision Trees

1. Introduction

A decision tree classifies by asking a sequence of questions, which makes it the most directly interpretable model in this course: the path from root to leaf is the explanation. This chapter covers how a tree chooses those questions, and where the approach runs out of road.

We work through the anatomy of a tree, the top-down greedy CART training procedure, and the impurity measures — Gini and entropy — that drive split selection, including a full hand calculation of a root split. We then handle continuous features via threshold splits, and the stopping criteria and regularisation hyperparameters that keep a tree from memorising its training set. The chapter closes with the geometric view: a single tree carves the feature space into axis-aligned rectangles, and that limitation is precisely the motivation for the ensembles that follow.

Learning Objectives

2. Theory

2.1 Decision Tree Anatomy

A decision tree predicts by routing an observation down a sequence of if/else tests, starting at the root and ending at a leaf. The leaf reached determines the predicted class, and the tests along the path form a rule that explains the prediction.

Outlook decision tree A decision tree determining whether to play based on outlook, humidity, and wind. Outlook decision tree A simple classification model for deciding whether to play Sunny Overcast Rain High Normal False True Outlook? ROOT · INTERNAL Humidity? Windy? INTERNAL NO decision leaf PLAY decision leaf PLAY decision leaf NO decision leaf Classification rules The tree can be expressed as the following logical conditions: IF Outlook = Overcast → PLAY ELIF Outlook = Sunny AND Humidity = High → NO ELIF Outlook = Sunny AND Humidity = Normal → PLAY ELIF Outlook = Rain AND Windy = False → PLAY ELSE Outlook = Rain AND Windy = True → NO Internal nodes evaluate conditions; terminal nodes provide the final recommendation. s*

2.2 Top-Down Greedy Training (CART Algorithm)

DT learning is a top-down, recursive, binary-split, greedy procedure:

  1. Start with all \(N\) training samples at the root node.
  2. Find the best split (feature, threshold) that maximizes the weighted decrease in impurity (Gini or Entropy).
  3. Partition the node's data into left/right children using that split.
  4. Recurse on each child until a stopping criterion fires (depth limit, pure node, min samples, etc.).
  5. Each leaf predicts the majority class (classification) or mean value (regression).

2.3 Impurity Measures

To choose a split we need a way to measure how mixed the classes are in a node. Two measures are in common use, and they behave similarly in practice:

Gini Index (CART)
Entropy + IG (ID3/C4.5)
Side-by-Side
\[ G(D) = 1 - \sum_{i=1}^{k} p_i^2 \]

Here \(p_i\) is the proportion of class \(i\) in node \(D\). The Gini index ranges from \(0\) for a pure node to \( \frac{k-1}{k}\) when the \(k\) classes are mixed in equal proportions.

Binary example: 70 pos, 30 neg → \(G = 1 - (0.7)^2 - (0.3)^2 = 1 - 0.49 - 0.09 = 0.42\).

\[ H(D) = -\sum_{i=1}^{k} p_i \log_2 p_i, \qquad \text{IG}(D, \text{split}) = H(D_{\text{parent}}) - \sum_{c \in \{\text{L},\text{R}\}} \frac{|D_c|}{|D|} H(D_c) \]

IG = reduction in entropy caused by the split. Range of \(H\): 0 (pure) → \(\log_2 k\) (max). We maximize IG; equivalently, we minimize weighted child entropy.

PropertyGiniEntropy
ComputationFaster (squares, no log)Slower (\(\log_2\) per class)
Range (binary)\([0, 0.5]\)\([0, 1]\) bit
Algorithm familyCART (scikit-learn default)ID3 / C4.5 / C5.0
Empirical differenceTypically produces very similar trees. Entropy can help with severe class imbalance.

2.4 Hand Calculation — Choose the Root Split (Play Golf, Gini)

Parent (root): 9 Yes, 5 No → \(G_{\text{root}} = 1 - (9/14)^2 - (5/14)^2 = 1 - 0.413 - 0.128 = 0.459\). Compute weighted Gini for splitting on each of the 4 categorical features:

Feature →OutlookTemperatureHumidityWindy
Child Gini (weighted) 5/14·G(S) + 4/14·G(O) + 5/14·G(R) 4/14·G(Ht)+6/14·G(Md)+4/14·G(Cl) 7/14·G(Hi)+7/14·G(Nm) 8/14·G(F)+6/14·G(T)
Compute 5/14·0.48 + 4/14·0 + 5/14·0.48 4/14·0.50+6/14·0.44+4/14·0.375 7/14·0.490 + 7/14·0.245 8/14·0.375+6/14·0.50
Weighted Gini 0.3429 ← Best (lowest) 0.4405 0.3675 0.4286

✅ Root-Split Winner

Outlook reduces parent impurity from 0.459 → 0.343, the largest drop of all 4 candidate features. CART therefore makes Outlook the root split. Repeat the same calculation independently on each child to grow deeper.

2.5 Continuous (Numerical) Features — Threshold Splits

For a continuous feature \(X\), sort its unique values, evaluate the midpoint between every pair as a candidate split \(X \le t\) vs. \(X > t\), and pick the \(t\) giving the lowest weighted child Gini.

Feature threshold selection workflow Sorted feature values are used to evaluate candidate thresholds with weighted impurity, then select the threshold with the minimum weighted score for a binary split. Selecting the optimal split threshold Evaluate every candidate boundary and choose the one with the lowest weighted impurity. 1 Start with sorted feature values Feature X values 1 3 4 7 8 10 Sorted in ascending order This defines the possible split boundaries. 2 Generate candidate thresholds Candidate thresholds t 2 3.5 5.5 7.5 9 1 10 Each threshold creates a possible binary partition between adjacent feature values. 3 Evaluate each candidate For every t, compute the weighted impurity: Gweighted = (nL/N) · GL + (nR/N) · GR Compare the resulting score across all five thresholds. 4 Choose the best split t* = argmint Gweighted Binary split: ≤ t* vs > t* s*

2.6 Stopping Criteria & Regularization Hyperparameters

Left to run, the recursion continues until every leaf is pure, which produces a tree that has memorized the training set. The following hyperparameters stop the growth early and control this:

HyperparameterWhat it doesTypical default / tuning range
max_depthStop growing once tree reaches this depth. Main control vs overfit.None (unlimited); try {3, 5, 8, 12, 20}
min_samples_splitMinimum samples in a node before it is eligible for splitting.2 (default); try {2, 5, 10, 20}
min_samples_leafMinimum samples that must land in each resulting leaf.1 (default); try {1, 3, 5, 10}
max_featuresNumber of features to randomly subset at each split (Random Forests).{"sqrt", "log2", d, 0.3·d}
ccp_alpha (pruning)Cost-complexity pruning. Higher α → aggressively prune small branches post-hoc.0.0; search via path

2.7 DT vs. kNN vs. NB — Grand Comparison

With three classifiers now covered, it is useful to compare them on the practical points that decide which one to reach for:

DimensionkNN (k=5)Naive BayesDecision Tree (depth 5)
Scaling required?✅ YES (critical for distance)Depends (Gaussian yes, MNB no)❌ NO (invariant to monotonic scaling)
Handles interactions?Implicitly via distance❌ No (independence)✅ Yes (hierarchical splits)
InterpretabilityLow (black-box distances)Medium (odds ratios)✅ High (if/then rules, feature_importances_)
Categorical featuresNeeds OHE/Gower✅ Native (MultinomialNB)OHE or ordinal (HistGradientBoosting native)
Prediction latencySlow O(n·d)Fast O(d)Fast O(depth)
Overfitting riskLow (kNN is stable)✅ Very low (high bias) High (unlimited depth → memorizes)

2.8 Geometric Interpretation of DTs — Axis-Aligned Rectangles

Credit-risk toy example: 30 loan applicants (16 default, 14 non-default). Features: Age, Account Balance ($). A shallow DT learns two splits:

  1. \(\text{Balance} \ge 50{,}000\)? (vertical line)
  2. Else \(\text{Age} \ge 45\)? (horizontal line in the left half-plane)
Decision tree rectangular regions by age and balance A decision boundary diagram showing balance greater than or equal to 50 thousand and age greater than or equal to 45, producing default and not default regions. Decision Tree Regions Classification boundaries across age and account balance Leaf: DEFAULT Balance ≥ 50K DEFAULT Age ≥ 45 Prob = 12/13 NOT DEFAULT Age < 45 Prob = 4/7 0 50K 200K BALANCE 70 60 50 45 35 25 AGE Balance ≥ 50K? Age ≥ 45 Rule path Balance ≥ 50K? NO Age ≥ 45? YES DEFAULT 12/13 YES NOT DEFAULT 4/7 NO i Decision trees create rectangular regions parallel to the feature axes. s*

Single-DT Geometric Limitations

3. Interactive Examples

Example 1: Gini & Entropy Calculations

A node contains 60 class-A samples and 40 class-B samples.

(a) Compute Gini.

\(G = 1 - 0.6^2 - 0.4^2 = 1 - 0.36 - 0.16 = \mathbf{0.48}\)

(b) Compute Entropy (bits).

\(H = -0.6 \log_2 0.6 - 0.4 \log_2 0.4 \approx -0.6(-0.737) -0.4(-1.322) \approx 0.442 + 0.529 = \mathbf{0.971}\) bits.

Example 2: Information Gain of a Split

Parent node (A=60, B=40) from Ex. 1 is split into: Left child (A=50, B=10) and Right child (A=10, B=30).

Compute Entropy-based Information Gain of this split.

H(parent) ≈ 0.971 bits (from Ex. 1b).

H(Left) = −5/6·log₂(5/6) −1/6·log₂(1/6) ≈ 0.650 bits. |L|/N = 60/100 = 0.6.

H(Right) = −1/4·log₂(1/4) −3/4·log₂(3/4) ≈ 0.811 bits. |R|/N = 0.4.

Weighted child H = 0.6·0.650 + 0.4·0.811 ≈ 0.714 bits.

IG = H(parent) − weighted H(children) = 0.971 − 0.714 = 0.257 bits.

Example 3: Tracing a Prediction + Reading Rule Path

Use the tree diagram in §2.1. Predict Play for Outlook=Sunny, Temp=Hot, Humidity=High, Windy=False.

  1. Root: Outlook = Sunny → descend left child (Humidity ?).
  2. Humidity = High → take High branch → leaf = NO.
Final prediction: No (don't play). The temperature and wind features were not even queried by this particular tree for this sample!

4. Numerical Solutions

Problem 1: Choose the Best Binary Split on a Numeric Feature

A candidate numeric feature X has values [1, 3, 4, 7] with labels [+, −, +, +]. Parent G = 0.375.

Evaluate two candidate thresholds \(t \in \{2, 5\}\) (X ≤ t vs. X > t) using weighted Gini. Pick the better split and compute its Gini decrease.

📘 Step-by-Step Solution

Step 1: t = 2. Left: {1=+} (pure, G=0), size 1/4. Right: {3=−,4=+,7=+}, GR = 1 − (1/3)² − (2/3)² ≈ 0.444, size 3/4. Weighted G = 0.25·0 + 0.75·0.444 ≈ 0.333.

Step 2: t = 5. Left: {1=+, 3=−, 4=+}, GL = 1 − (2/3)² − (1/3)² ≈ 0.444, size 3/4. Right: {7=+}, GR = 0, size 1/4. Weighted G = 0.75·0.444 + 0.25·0 ≈ 0.333.

Step 3: Both splits tie in weighted Gini (0.333). Both give a decrease of 0.375 − 0.333 = 0.042. A tie-breaking rule (lower index feature / leftmost threshold) picks one.

Problem 2: Effect of max_depth on Overfitting

You train two trees on Adult Census (26K train rows): Tree A (max_depth = 3) → train-AUC 0.86, test-AUC 0.855. Tree B (max_depth = None, unlimited) → train-AUC 0.998, test-AUC 0.84.

📘 Diagnostics & fix

Diagnosis: Tree A = healthy low-bias/moderate-variance fit (tiny 0.005 train–test gap). Tree B = severe overfitting: train AUC near-perfect, test AUC worse than Tree A by 1.5 points.

Fix: Limit capacity via one or more of:

  • Reduce max_depth (GridSearch {2..10}) — single strongest lever.
  • Increase min_samples_leaf to {5, 10, 20} so leaves can't memorize small pockets.
  • Apply Cost-Complexity Pruning (tune ccp_alpha).
  • OR: move to an ensemble (Random Forest / Gradient Boosting) — they solve DT overfitting architecturally (next units!).

Problem 3: Feature Importances from Split Counts

A small tree has 5 splits total: feature A used 3 times (weighted Gini decreases of 0.40, 0.30, 0.10), feature B used 2 times (decreases 0.25, 0.05), feature C never used. Compute normalized feature importances.

📘 Step-by-Step

Total decrease = (0.40+0.30+0.10) + (0.25+0.05) + 0 = 1.10.

Importances: A = 0.80/1.10 ≈ 72.7 %, B = 0.30/1.10 ≈ 27.3 %, C = 0 %. (These sum to 1.0. scikit-learn normalizes the total impurity decrease exactly this way.)

5. Try It Yourself

Problem 1 — Gini for 3 Classes

Node has classes {A:5, B:3, C:2}. Compute Gini impurity.

\(G = 1 - (0.5)^2 - (0.3)^2 - (0.2)^2 = 1 - (0.25+0.09+0.04) = 1 - 0.38 = \mathbf{0.62}\). (Max possible Gini for k=3 is \(2/3 \approx 0.667\) — this node is close to uniform mixing.)
Problem 2 — Weighted Child Gini (2-Way Split)

Split a 20-sample parent into Left (12 samples: 10 pos, 2 neg) and Right (8 samples: 1 pos, 7 neg). Compute weighted Gini of the split and compare it to parent G = 0.48. Did purity improve? By how much?

GL = 1 − (10/12)² − (2/12)² ≈ 0.278; GR = 1 − (1/8)² − (7/8)² ≈ 0.219.
Weighted Gini = 0.6·0.278 + 0.4·0.219 ≈ 0.254.
Purity improved by 0.480 − 0.254 = 0.226 (large drop → good split!).
Problem 3 — Overfitting Diagnosis

Tree-C has max_depth=10, min_samples_leaf=1. Its train accuracy = 0.998 but test accuracy = 0.712 on the same task as Problem 2 of §4.

(i) What is this phenomenon? (ii) Name 3 knobs to fix it.

(i) Severe overfitting (memorization of training-set noise).

(ii) Any three valid regularizers from: lower max_depth, higher min_samples_leaf, higher min_samples_split, max_features (if ensembling), ccp_alpha cost-complexity pruning, early stopping, switching to a Random Forest / Gradient Boosting ensemble.

6. Interactive Quiz

Answer all 6 questions. Click an option for instant feedback.

Your score: 0 / 6

7. Key Takeaways

  1. CART = Top-down greedy binary splits. At each node, sweep every (feature, threshold) pair; keep the one minimizing weighted child Gini (Entropy, MSE, MAE for regression).
  2. Gini vs. Entropy rarely produce materially different trees. Gini is faster default; Entropy/IG can help with heavy imbalance or when using information-theoretic justifications.
  3. Numeric features → try every midpoint as threshold and pick the best binary split (X ≤ t vs. > t). This is why DTs are scale-invariant: only the order matters.
  4. DTs overfit unless you regularize. Unlimited-depth DTs memorize noise. The single most effective lever: max_depth. Combine with min_samples_leaf and optionally ccp_alpha pruning.
  5. D strengths: No scaling, native handling of mixed types (with OHE or HistGBT), interpretable rules, built-in feature importances, fast prediction. Weakness: high variance → unstable trees. Solution: ensembles!
  6. Grand comparison: NB fastest/baseline & text king; kNN simplest lazy distance method; DTs best for rule-based interpretability and strong tabular baselines. Enemies of DT: deep unlimited trees, tiny leaf samples.

8. Common Pitfalls

  1. Training unlimited-depth DTs on default scikit-learn settings. This almost always overfits. Always set max_depth at a minimum.
  2. Using Gini / Entropy on regression trees. For regression, split on MSE / MAE reduction — not Gini. scikit-learn's DecisionTreeRegressor does this.
  3. Dropping feature names / not plotting the tree. DTs are interpretable by design — leverage this! Use tree.plot_tree or export_graphviz.
  4. One-hot encoding high-cardinality categorical features into a deep CART tree. This creates imbalanced splits and blows up depth. Use HistGradientBoostingClassifier's categorical_features or target encoding instead.
  5. Believing feature_importances_ measure causal importance. They measure correlation-driven impurity reduction on the training set. Two correlated features can split credit arbitrarily. Use permutation importance + SHAP for robust interpretations.
  6. Comparing DT (single) against a tuned ensemble and concluding "trees are bad." Single trees are the weak learner. The power of DTs is as base learners inside Random Forest / Gradient Boosting.